//
//  146_LRU 缓存.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/15.
/**
 https://leetcode.cn/problems/lru-cache/description/
 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 实现 LRUCache 类：
 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 示例：

 输入
 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 输出
 [null, null, null, 1, null, -1, null, -1, 3, 4]

 解释
 LRUCache lRUCache = new LRUCache(2);
 lRUCache.put(1, 1); // 缓存是 {1=1}
 lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
 lRUCache.get(1);    // 返回 1
 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
 lRUCache.get(2);    // 返回 -1 (未找到)
 lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
 lRUCache.get(1);    // 返回 -1 (未找到)
 lRUCache.get(3);    // 返回 3
 lRUCache.get(4);    // 返回 4
 */

import UIKit

extension LRUCache {
    static func QA()  {
        let lRUCache = LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        print(lRUCache.get(1) == 1);    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        print(lRUCache.get(2) == -1);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        print(lRUCache.get(1) == -1);    // 返回 -1 (未找到)
        print(lRUCache.get(3) == 3);    // 返回 3
        print(lRUCache.get(4) == 4);    // 返回 4
    }
}


/// 哈希表+双向链表
class LRUCache  {
    
    class LRULinkNode {
        let key: Int
        var value: Int
        var prev: LRULinkNode?
        var next: LRULinkNode?
        init(key: Int, value: Int, prev: LRULinkNode? = nil, next: LRULinkNode? = nil) {
            self.key = key
            self.value = value
            self.prev = prev
            self.next = next
        }
    }
    
    private var dict = [Int: LRULinkNode]() // 存储数据的哈希表
    private var capacity: Int = 2 // 容量
    // 虚拟头结点
    private let first = LRULinkNode(key: Int.min, value: Int.min)
    // 虚拟尾节点
    private let last = LRULinkNode(key: Int.max, value: Int.max)

    
    init(_ capacity: Int) {
        self.capacity = capacity
        first.next = last
        last.prev = first
    }
    
    func get(_ key: Int) -> Int {
        guard let node = dict[key] else {
            return -1
        }
        removeNode(node)
        insertFirst(node)
        return node.value
    }
    
    func put(_ key: Int, _ value: Int) {
        if let node = dict[key] {
            node.value = value
            removeNode(node)
            insertFirst(node)
        } else {
          
            if dict.count == capacity {
                // 删除最近没有使用的key-value
                if let key = last.prev?.key,
                   let deletNode = dict.removeValue(forKey: key) {
                    removeNode(deletNode)
                }
            }
            // 添加节点
            let node = LRULinkNode(key: key, value: value)
            dict[key] = node
            insertFirst(node)
        }
    }
}

extension LRUCache {
    
    /// 双向链表中删除节点
    private func removeNode(_ node: LRULinkNode) {
        let prev = node.prev
        let next = node.next
        prev?.next = next
        next?.prev = prev
        
    }
    /// 把节点插入到虚拟头节点first后面
    private func insertFirst(_ node: LRULinkNode) {
        let next = first.next
        first.next = node
        node.prev = first
        node.next = next
        next?.prev = node
    }
}
